1. Field of the Invention
The present invention is related to an improved data processing system. Particular aspects relate to the World Wide Web, databases, and transaction processing systems. A more particular aspect is related to the caching of dynamic documents on the World Wide Web.
2. Related Art
Complex objects can be expensive and time-consuming to create. Caching complex objects reduces the cost of creation by minimizing the frequency of regeneration of identical objects. The cost of generating objects in the absence of caching is reflected to end-users in terms of: (a) increased response time; and (b) inconsistent response time.
Consider a Web-based server with a very high frequency of access, whose content contains a high ratio of dynamic to static pages. Assume further that the content of the dynamic pages change frequently. When a page becomes obsolete and is flushed from cache: the first user who requests that page will experience a cache-miss, causing regeneration of that page. Because the cost (and therefore, the physical wall-clock time) of creating that page is great, there may be a significant probability of several other requests for that same page arriving before it is replaced in cache. This can result in many simultaneous regenerations of the same page, and resultant wasted resources. A specific instance of this scenario is a sports server, for example, serving the Olympics. Results for the currently active sports are arriving at a high rate, causing the pages that reflect scores to change frequently; at the same time users are requesting those pages at a high rate to see the status of the event. Because the pages are being invalidated frequently, a significant number of requests cause the page to be regenerated. Thus there is a need for a system which maintains the validity of the page in one or more caches at all times, and automatically replaces it when the underlying data changes, thereby reducing system loading and significantly improving response time. The present invention addresses such a need.
Another problem is manifested on web servers where consistency of response time is critical. Once users have accessed a site, or a location within a site, keeping their attention may be of prime importance. For example, a Web-based mail-order catalog may want to encourage browsing; if the user gets bored waiting for pages he or she may well leave for other entertainment.
The present invention is of particular importance to proxy caches (see "Caching Proxies: Limitations and Potentials" by M. Abrams et. al., Fourth International World Wide Web Conference Proceedings, Dec. 1996, pp. 119-133; and "World-Wide Web Proxies", A. Luotonen and K. Altis, in Computer Networks and ISDN Systems, vol. 27 (1994) pp. 147-154). One of the problems with most proxy caches on the Web today is that there is no way to determine if pages in the caches are obsolete. For this reason, most proxy caches do not store dynamic pages. The present invention solves this problem and provides a powerful method for maintaining current copies of both dynamic and static data in multiple caches distributed across a network.
Thus, there is a need for a method and system for automatically detecting changes in the underlying data and efficiently replacing objects dependent on that data in one or more caches as the primary mechanism for cache maintenance. The present invention addresses such a need. Existing cache invalidation schemes typically involve some variant of (a) aging, in which items which have not been referenced within some period of time are removed from cache, and (b) forceful deletion of items known to be obsolete.
A considerable amount of work has been done in the area of cache coherence for shared-memory multiprocessors (see "Computer Architecture: A Quantitative Approach" by J. Hennessy and D. Patterson, Morgan Kaufmann Publishers, Inc., 1996). In shared-memory multiprocessors, no caches are allowed to contain obsolete values. For example, suppose the variable x=99 is stored in caches belonging to processors p1, p2, and p3. Another processor p4 wishes to change the value of x to 255. Before p4 can update x, it must ensure that p1, p2, and p3 have invalidated x from their caches. It is only at this stage that p4 can update x.
However, Web caches operate in a different environment from the environment that processor caches operate in. In processor caches, incorrect behavior can result if a cache contains a value which is even a fraction of a second out of date. For Web caches, it is often acceptable for a cached Web document to be slightly out of date. For example, suppose that a Web document w is contained in three caches (c1, c2, and c3) and that the Web document w is managed and updated by a data source d. Using the multiprocessor cache coherence approach, the data source d must first invalidate the Web document w from c1, c2, and c3 before updating the Web document. Thus, the multiprocessor cache coherence approach would cause the Web document w to be absent from the cache for a certain period of time whenever the Web document was updated. Requiring the data source d to invalidate the Web document w in caches before performing the update, results in slower updates and cache misses during the extra time that the Web document w is not present in the cache. Thus, there is also a need for a method and system which provides faster updates and higher cache hit rates. The present invention addresses such a need.